home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / pascal / exarray.com / EXTARRAY.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1989-08-19  |  8.6 KB  |  280 lines
  1. Unit ExtArray; {Extended Generic Fully-Dynamic Arrays}
  2. {$R-,O+,V-,S-}
  3.  
  4. { The ExtendedArray is closely related to the MaxArray, but is limited only }
  5. { by your available diskspace. HOWEVER, Random access performance can only  }
  6. { be described as AWFUL!  Sequential and nearly-sequential access times are }
  7. { quite good (only off the standard array by a small constant), but random  }
  8. { access is terrible.  This is due to the way the array is stored on disk.  }
  9.  
  10. { The idea behind the Extended array is simple.  Divide the array into a    }
  11. { number of "Lobes", and then store these lobes on disk.  Keep several of   }
  12. { them on the Heap at all times, and simply swap lobes to and from disk as  }
  13. { required.  This is why sequential access is so good.  Unfortunately, as   }
  14. { the total number of lobes goes up, the chances of finding the indexed     }
  15. { element on the Heap go down, causing the Extended Array to spend (MUCH)   }
  16. { time swapping lobes back and forth (in the Random-Access case).           }
  17.  
  18. { Without doing the appropriate performance analyses, I can not say for     }
  19. { sure how rapidly the performance degrades, but I have done sufficient     }
  20. { testing to make a "seat-of-the-pants" analysis which indicates (to me)    }
  21. { that it is best to keep Extended Arrays (which need a lot of random       }
  22. { accessing) to approximately one-half on disk and one-half on the Heap.    }
  23. { As the AutoInit method attempts to keep about 300k bytes of the Array on  }
  24. { the Heap, My guess-work says that for arrays of up to about 600-700kbytes }
  25. { byte size, random performance should be satisfactory.  Using the other    }
  26. { initialization method (ManualInit), you can force the Heap portion of the }
  27. { Array up to 500k bytes, which should yield good performance for sizes up  }
  28. { to 1.0 million bytes.                                                     }
  29.  
  30. { NOTE: As with MaxArrays, ExtendedArrays are Indexed 0..MaxSize-1 }
  31.  
  32. { All resemblance to MaxArray methods is Entirely intended! }
  33.  
  34. INTERFACE
  35.  
  36. Uses X_Table,FlexPntr;
  37.  
  38. Type
  39.   ExtendedArray = Object
  40.  
  41.     ElSize    : Word;
  42.     MaxEl     : LongInt;
  43.     WorkSpace : FlexPtr;   {Currently useable Lobe provided by ExtendedTable}
  44.     Lobes     : Word;
  45.     BuffSize  : Word;
  46.     Table     : ExtendedTable;
  47.     Current   : Word;      {Index of WorkSpace Lobe}
  48.  
  49.     Procedure Create;
  50.  
  51.     Procedure AutoInit (MaxElements : LongInt; ElementSize : Word);
  52.  
  53.     Procedure ManualInit (MaxElements : LongInt; ElementSize : Word;
  54.                           MaxLobeSize : Word);
  55.     Procedure Destroy;
  56.  
  57.     Procedure Accept (Var El; Index : LongInt; Size : Word);
  58.                                        {Assign the Indexth El}
  59.  
  60.     Procedure Retrieve (Var El; Index : LongInt; Size : Word);
  61.                                          {Get the Indexth El}
  62.  
  63.     Procedure Copy (From : ExtendedArray);
  64.                               {Target *MUST* already be initialized}
  65.                               {to the EXACT same parameters as From}
  66.                               {this will save checking for sufficent}
  67.                               {available Memory!}
  68.  
  69.  
  70.     Procedure Swap (I,J : LongInt); {Swap the Ith and Jth Elements}
  71.  
  72.     Function MaxSize : LongInt;   {Report Array Length}
  73.     Function ElemSize : Word;  {Report Element Size}
  74.  
  75.   End;
  76.  
  77. IMPLEMENTATION
  78.  
  79. Procedure ExtendedArrayError (Num : Byte);
  80. Begin
  81.   WriteLn;
  82.   Write ('ExtendedArray ERROR: ');
  83.   Case Num of
  84.             0 : WriteLn ('Attempted Init on Un-Created or Initialized ExtendedArray.');
  85.             2 : WriteLn ('Attempted Accept with Incorrect Size Variable.');
  86.             3 : WriteLn ('Attempted Accept on Un-Initialized ExtendedArray.');
  87.             4 : WriteLn ('Attempted Retrieve with Incorrect Size Variable.');
  88.             5 : WriteLn ('Attempted Retrieve with Un-Initialized ExtendedArray.');
  89.             6 : WriteLn ('***** INDEX OUT OF BOUNDS *****');
  90.             7 : WriteLn ('Attempted Copy on Un-Created or Initialized ExtendedArray.');
  91.            11 : WriteLn ('Insufficent Memory to perform Swap operation.');
  92.            12 : WriteLn ('Attempted Illegal Copy operation.');
  93.            13 : WriteLn ('Selected LobeSize is Too Large.');
  94.           End;
  95.   WriteLn ('**** PROGRAM TERMINATED ****');
  96.   WriteLn;
  97.   Write ('Press <Return> to Continue.... ');
  98.   ReadLn;
  99.   HALT (0)
  100. End;
  101.  
  102. Procedure ExtendedArray.Create;
  103. Begin
  104.   Table.Create;
  105.   WorkSpace := Nil;
  106.   ElSize := 0;
  107.   MaxEl := 0;
  108.   Lobes := 0;
  109.   BuffSize := 0;
  110. End;
  111.  
  112. Procedure ExtendedArray.AutoInit (MaxElements : LongInt; ElementSize : Word);
  113. Var
  114.   NumLobes : Word;
  115. Begin
  116.   NumLobes := 8;
  117.   While ((MaxElements*ElementSize) Div NumLobes) > 37500 {keeps Heap to < 350k}
  118.                                     do NumLobes := NumLobes + 1;
  119.   BuffSize := ((MaxElements*ElementSize) Div NumLobes);
  120.   BuffSize := BuffSize - (BuffSize Mod ElementSize);
  121.   While LongInt(BuffSize * LongInt (NumLobes)) <
  122.         LongInt(MaxElements * LongInt (ElementSize))
  123.                             do BuffSize := BuffSize + ElementSize;
  124.   Lobes := NumLobes;
  125.   Current := Lobes+1;
  126.   Table.Init (NumLobes,BuffSize);
  127.   ElSize := ElementSize;
  128.   MaxEl := MaxElements
  129. End;
  130.  
  131. Procedure ExtendedArray.ManualInit (MaxElements : LongInt; ElementSize : Word;
  132.                                    MaxLobeSize : Word);
  133. Var
  134.   NumLobes : Word;
  135.   Temp     : LongInt;
  136. Begin
  137.   NumLobes := 8;
  138.   While ((MaxElements*ElementSize) Div NumLobes) > MaxLobeSize
  139.                                     do NumLobes := NumLobes + 1;
  140.   Temp := ((MaxElements*ElementSize) Div NumLobes);
  141.   Temp := Temp - (Temp Mod ElementSize);
  142.   While LongInt(Temp * LongInt (NumLobes)) <
  143.         LongInt(MaxElements * LongInt (ElementSize))
  144.                             do Temp := Temp + ElementSize;
  145.  
  146.   If Temp > 65521 Then ExtendedArrayError (13);
  147.   BuffSize := Word(Temp);
  148.   Lobes := NumLobes;
  149.   Current := Lobes+1;
  150.   Table.Init (NumLobes,BuffSize);
  151.   ElSize := ElementSize;
  152.   MaxEl := MaxElements
  153. End;
  154.  
  155. Function ExtendedArray.MaxSize : LongInt;
  156. Begin
  157.   MaxSize := MaxEl
  158. End;
  159.  
  160. Function ExtendedArray.ElemSize : Word;
  161. Begin
  162.   ElemSize := ElSize
  163. End;
  164.  
  165. Procedure ExtendedArray.Destroy;
  166. Begin
  167.   Table.Destroy;
  168.   WorkSpace := Nil;
  169.   ElSize := 0;
  170.   MaxEl := 0;
  171.   Lobes := 0;
  172.   BuffSize := 0;
  173. End;
  174.  
  175. Procedure Map (E : ExtendedArray; Index : LongInt; Var N : LongInt; Var K : Word);
  176. Var
  177.   I : Word;
  178.   J : LongInt;
  179. Begin
  180.   I := 0;
  181.   J := Index;
  182.   While J >= E.BuffSize do
  183.     Begin
  184.       J := J-E.BuffSize;
  185.       I := I + 1
  186.     End;
  187.   K := I;
  188.   N := Word(J)
  189. End;
  190.  
  191. Procedure ExtendedArray.Accept (Var El; Index : LongInt; Size : Word);
  192. Var
  193.   I    : Word;
  194.   J    : LongInt;
  195.   Temp : FlexSpace Absolute El;
  196. Begin
  197.   If Index >= MaxEl Then ExtendedArrayError (6);
  198.   J := Index*ElSize;      {Compute Actual Index}
  199.   Map (Self,J,J,I);
  200.  
  201.   If I <> Current Then
  202.     Begin
  203.       WorkSpace := Table.Retrieve (I);
  204.       Current := I
  205.     End;
  206.  
  207.   If WorkSpace <> Nil
  208.     Then
  209.       If Size = ElSize
  210.         Then
  211.           Begin
  212.             Move (Temp,WorkSpace^.Flex[J],ElSize);
  213.             If Current <> I Then
  214.               Table.Update (I,WorkSpace)
  215.           End
  216.         Else
  217.           ExtendedArrayError (2)
  218.     Else
  219.       ExtendedArrayError (3)
  220. End;
  221.  
  222. Procedure ExtendedArray.Retrieve (Var El; Index : LongInt; Size : Word);
  223. Var
  224.   I    : Word;
  225.   J    : LongInt;
  226.   Temp : FlexSpace Absolute El;
  227. Begin
  228.   If Index >= MaxEl Then ExtendedArrayError (6);
  229.   J := Index*ElSize;
  230.   Map (Self,J,J,I);
  231.  
  232.   If I <> Current Then
  233.     Begin
  234.       WorkSpace := Table.Retrieve (I);
  235.       Current := I
  236.     End;
  237.  
  238.   If WorkSpace <> Nil
  239.     Then
  240.       If Size = ElSize
  241.         Then
  242.           Move (WorkSpace^.Flex[J],Temp,ElSize)
  243.         Else
  244.           ExtendedArrayError (4)
  245.     Else
  246.       ExtendedArrayError (5)
  247. End;
  248.  
  249. Procedure ExtendedArray.Copy (From : ExtendedArray);
  250. Var
  251.   I : Word;
  252. Begin
  253.   If (From.ElSize <> ElSize) or (From.MaxEl <> MaxEl) or (Lobes <> From.Lobes)
  254.     Then ExtendedArrayError (12);
  255.   For I := 0 to Lobes do
  256.     Begin
  257.       WorkSpace := From.Table.Retrieve (I);
  258.       Table.Update (I,WorkSpace)
  259.     End
  260. End;
  261.  
  262. Procedure ExtendedArray.Swap (I,J : LongInt);
  263. Var
  264.   Ith  : FlexPtr;
  265.   Jth  : FlexPtr;
  266. Begin
  267.   GetMem (Ith,SizeOf(FlexCount) + ElemSize);
  268.   GetMem (Jth,SizeOf(FlexCount) + ElemSize);
  269.   If (Ith = Nil) or (Jth = Nil) Then ExtendedArrayError(11);
  270.   Retrieve (Ith^.Flex,I,ElemSize);
  271.   Retrieve (Jth^.Flex,J,ElemSize);
  272.   Accept (Ith^.Flex,J,ElemSize);
  273.   Accept (Jth^.Flex,I,ElemSize);
  274.   FreeMem (Ith,SizeOf(FlexCount) + ElemSize);
  275.   FreeMem (Jth,SizeOf(FlexCount) + ElemSize)
  276. End;
  277.  
  278. BEGIN
  279.   HeapError := @HeapErrorTrap  {Exported from FlexPntr}
  280. END.